package subjectlist;

/**
 * 给定主字符串s与模式字符串p，判断p是否是s的子串，如果是，则找出p在s中第一次出现时的下标
 */
public class J如何实现字符串的匹配 {

    /**
     * 方法功能：求字符串的next的数组
     * 输入参数:p为字符串，next为p的next的数组
     */
    public static void getNext(String p,int[] next){
        int i=0,j=-1;
        next[0]=-1;
        while (i < p.length()) {
            if (j == -1 || p.charAt(i) == p.charAt(j)) {
                i++;
                j++;
                next[i]=j;
            }else{
                j=next[j];
            }
        }
    }

    public static int match(String s,String p,int [] next){
        //检查参数的合理性,s.的长度一定不小于p的长度
        if (s == null || p == null) {
            System.out.println("参数的不合理");
            return -1;
        }

        int slen=s.length();
        int plen=p.length();
        //p肯定不是s的字串
        if(slen<plen){
            return -1;
        }
        int i=0,j=0;
        while (i < slen && j < plen) {
            System.out.println("i="+i+","+"j="+j);
            if (j == -1 || s.charAt(i) == p.charAt(j)) {
                //如果相同，则继续比较后面的字符
                i++;
                j++;
            }else {
                j=next[j];
            }
        }
        if (j >= plen) {
            //匹配成功
            return i-plen;
        }
        return -1;
    }

    public static void main(String[] args) {
        String s="abababaabcbab";
        String p="abaabc";
        int len=p.length();
        int [] next=new int[len+1];
        getNext(p,next);
        System.out.println("next数组："+next[0]);
        for (int i = 1; i <len ; i++) {
            System.out.print(","+next[i]);
        }
        System.out.println();
        System.out.println("匹配结果为："+match(s,p,next));

        String a="aaaaassssd";

        if(a.contains("aass")){
            System.out.println(true);
        }
    }

}

